808G - Anthem of Berland - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;


#define ElGed_Sevawy  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ld long double
#define el '\n'
#define F first
#define S second
#define sz(x) (int)(x).size()

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(gen);
}

const ll N = 1e5 + 3, M = 1e6 + 5, MOD1 = 1e9 + 7, MOD2 = 1e9 + 9, lg = 21, INF  = 2e18 + 5, P1 = 29, P2 = 31;
int pi[N];
void comput_pi(string &s){
    int n = sz(s);
    pi[0] = 0;
    for(int i = 1; i < n; i++){
        int j = pi[i - 1];
        while (j && s[i] != s[j])
            j = pi[j - 1];
        if(s[i] == s[j]) j++;
        pi[i] = j;
    }
}
string s, t;
vector<vector<int>>dp;
int dp2[N][30];
int solve2(int j, int x){
    if(~dp2[j][x])
        return dp2[j][x];
    int k = j;
    while (k && t[k] != x + 'a')
        k = pi[k - 1];
    k += t[k] == x + 'a';
    return dp2[j][x] = k;
}
int solve(int i, int j){
    if(i == sz(s))
        return 0;
    int &ret = dp[i][j];
    if(~ret) return ret;
    ret = 0;
    if(s[i] != '?'){
        int k = solve2(j, s[i] - 'a');
        ret = solve(i + 1, k) + (k == sz(t) - 1);
    }else{
        for(char c = 'a'; c <= 'z'; c++){
            int k = solve2(j, c - 'a');
            ret = max(ret, solve(i + 1, k) + (k == sz(t) - 1));
        }
    }
    return ret;
}
void go() {
    cin >> s >> t;
    if(sz(t) > sz(s)){
        cout << 0 << el;
        return;
    }
    t.push_back('#');
    comput_pi(t);
    dp.resize(sz(s) + 2, vector<int>(sz(t) + 2, - 1));
    ::memset(dp2, -1, sizeof dp2);
    cout << solve(0, 0) << el;
}
int32_t main() {
    ElGed_Sevawy
    int tc = 1;
    //cin >> tc;
    while (tc--)
        go();
}